Chapter 2

Introduction to Linked List

Linked List: It consists of a sequence of nodes (memory spaces), each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes.

Array	ArrayList	Linked List
Array is fixed size	Size can change	Size can change
An array element can be accessed directly by its index	An arraylist element can also be accessed by its index directly	Each element cannot be accessed directly. Nodes in a linked list must be accessed sequentially
Array elements are adjacent in memory	Elements adjacent in memory	Nodes may not be adjacent to each other
No new element can be added	To add or remove an element all existing elements need to be shifted to one side	Add or remove can be done without shifting elements

How to create a linked list

• How to allocate space for a node dynamically?
• By creating an object of class node
• How to allow a node to link or reference to another node?
• The node class must contain a reference variable capable to referencing object of the same class

Self-referential class: A class that includes an instance variable or variables that can hold a reference to an object of the same class.

public class LLStringNode {

private String info;

private LLStringNode next;

public LLStringNode(String info)

{

this.info = info;

next = null;

}

}

Question: What is the consequence of the following line?

LLStringNode node1 = new LLStringNode(“Hanna”);

SEE class LLStringNode.java.

Another Constructor

public LLStringNode(String info, LLStringNode refNode){

this.info = info;

next = refNode;

}

Linked List Traversal

Suppose you have a linked list named letters. How will you traverse all the nodes in that list?

• Set currNode to the first node in the list
• while(currNode is not pointing off the list)
• display the information at currNode
• change currNode to point to the next node on the list

Question: Refine this algorithm gradually to convert it to a piece of code

public void Traverse() {

LLStringNode currNode = letters; //NOTE: You DON’T create a new node using constructor.

while ( currNode != null) {

//You can do whatever you like

System.out.println(currNode.info);

currNode = currNode.next; //Advance towards the next node

}

}

v Pitfall: Falling off the End of a List

§ If currNode is at the end of the list and you execute currNode = currNode.next; currNode will be set to null. You are now at the end of the list. If you execute this statement again, it will give you an error.

Inserting a node at the beginning of a list

• Create a standalone node.
• Link the node’s reference variable link to the first node of the already existing list.
• Now link the reference variable letters to the new node.

LLStringNode newNode = new LLStringNode(“Barbara”);

newNode.next = letters;

letters = newNode;

Deleting a node at the beginning of a list

• Reference variable letters points to the first node.
• Make letters point to the second node.

letters = letters.next;

Questions:

1. How will you insert a node at the end of a list?
2. How will you insert a node at the middle of a list?
3. How will you delete a node at the end of a list?
4. How will you delete a node in the middle of a list?